快手 Android 内存分配器优化探索 (一)
文 / 李锐
编辑 / finn
本文共6770字，预计阅读时间15分钟。
01
简介
Android 默认的 native 内存分配器是 Google 一直“疏于管理”的领域，jemalloc 是大部分 Android 版本的默认内存分配器，Google 只是在 Facebook jemalloc 的标准开源版本上做了小量定制修改。直至 Android 11 ，官方开始主推 Google 自研的 scudo 分配器，这一分配器胜在安全性，但性能不是强项，个别注重性能的国内手机厂商 ROM 在高版本甚至从默认的 scudo 切回了 jemalloc。
快手 App 作为一款以音视频为主的国民级应用，有上百个 so，存在大量 native 内存分配需求。我们从去年开始，以优化 32 位进程虚拟内存占用为初衷，深入研究并实践了 Android 内存管理机制与内存分配器的诸多技术细节，首创了 Android App 进程的 native 内存分配器替换方案。该方案支持所有 Android 应用集成，同时支持编译时替换与运行时替换两种方案，为 Android 应用的 native 内存优化打开了更多想象空间。
本系列文章将通过以下四个方面分享从操作系统内存管理机制到用户态内存分配器的具体实现细节，展示快手内存分配器优化探索的成果及其技术原理。
Linux 内存管理和内存分配器基础
jemalloc 源码设计剖析核心优缺点
Google 优化历程与业界近年来探索
快手 Android 内存分配器优化实践
02
Linux 内存管理
本节将介绍 Android 平台内存管理相关背景，并介绍部分当代内存分配器设计细节。
虚拟内存
操作系统和 MMU 硬件在程序和物理内存之间增加了一层虚拟内存，实现了进程虚拟地址和物理地址之间的隔离，以及进程与进程之间的地址隔离。当虚拟内存真正被访问时，内核才会为其分配物理内存。Linux 内核内存分配是基于分页的，这种按需分配物理页的方式称之为 demand paging，简化流程如下图。
MMU: Memory Management Unit，操作系统用来管理虚拟地址和物理地址映射关系的硬件。
TLB：Translation Lookaside Buffer，用于加速页表查找，即加快虚拟地址物理地址转换的硬件。
Linux 内存分配
malloc 不是一个系统调用，而是用户态分配内存的一组普通函数中使用最为广泛的一个。除了 malloc 以外，这组函数还有 posix_memalign, calloc, realloc。事实上，真正执行申请内存的系统调用是 brk/sbrk 和 mmap。
根据页面是否共享以及 mapping 是否有文件作为 backend，mmap 的映射可以分为四种：私有匿名映射、共享匿名映射、私有文件映射以及共享文件映射。mmap 对应 Linux 内核管理的 vma，这个结构具体叫作 vm_area_struct，vm_area_struct 以链表形式存储，控制 vma 的起止地址、prot 权限设置以及 flags 设置。
这里通过摘自《Computer Systems: A programer's Perspective》的一幅图来辅助阐述：
对于系统库，如 libc.so、虚拟机的 libart.so，分配的内存页面都是共享的，基于共享的特性可以节省内存，对应上图中的“Shared libraries"。
对于进程数据，如 [data] 段、内存分配器申请的进程堆内存，分配的内存页面都是私有的，基于私有特性可以与其他进程隔离保证安全和隐私。
也就是说，通过 mmap 申请私有匿名映射页面，可以完成用户态进程的堆内存的大块连续区域申请。内存分配器就是在这部分地址区间上管理空闲空间，面对后续的内存块分配与释放请求持续耕耘。
brk 取意于 program break，由于虚拟内存的发展，brk 已经过时了(legacy)，感兴趣的同学可以在 mac 上用 manual 命令查看相关描述：
The brk and sbrk functions are historical curiosities left over from earlier days before the advent of virtual memory management.
如果进程的 maps 里出现了较大范围 [heap] 的 vma，则说明此设备在使用 brk 分配堆内存。根据线上数据经验，这些设备集中在 Android 6.0 及以下。
更多的高版本 Android 设备使用现代内存分配器，对应申请的页面全是通过 mmap 申请私有映射页面，来存储进程自己的堆内存。查看高版本 Android 的进程 maps，可以看到堆内存的 vma 名字叫作 [anon:libc_malloc]，scudo 的 vma 名称与此略有区别，后文再详细展开。
一个典型的 jemalloc 的 vma 如下图：
Linux 内存释放
与内存分配同理，free 也不是释放内存的系统调用，Linux 提供的内存释放接口是 mmap 和 madvise。
首先，可以通过 munmap 进行内存释放，与 mmap 功能相对应，munmap 会解除对应 page 页的映射与占用，page 对应的虚拟内存和物理内存都会一并释放。这一流程比较简单，除此之外，我们还可以通过 mmap 的参数组合来释放内存：
prot：提供此参数的本意是指定 mapping 的保护要求，即 vma 权限设置。参数可选内容为 PROT_READ/PROT_WRITE/PROT_EXEC/PROT_NONE，分别代表可读、可写、可执行和不可访问。其中，读、写、执行都比较好理解，而 PROT_NONE 代表的不可访问的特性会在内存分配器释放内存时使用，如在 jemalloc 内部实现中用于执行 page 的 decommit。该方式的特点是在释放物理内存的同时，会“占坑” mapping 对应的地址区间，不会因其他 mmap 请求被分配出去，下次分配内存时使用 MAP_FIXED 重新 commit。
flags：此 flag 可以通过设置 MAP_SHARED 和 MAP_PRIVATE 来控制是否共享。除此之外，还有一个 flag 是 MAP_FIXED，代表在指定起始地址申请 mapping，此 flag 会在内存分配器的内部实现中搭配上文所述 PROT_NONE 使用，用于实现内存页面的 commit。使用 PROT_NONE “占坑”的地址空间，可以通过 MAP_FIXED 来指定 mapping 分配的起始地址再次分配，进而继续复用既有的虚拟内存地址区间保证地址不变。
除了 mmap 相关方法之外，使用最为广泛的释放内存的系统调用是 madvise。
madvise 的名字为 memory advise，代表用户程序给 kenerl 传递参数，提供使用内存的建议。
内存释放相关的 advice 参数为 MADV_FREE 和 MADV_DONTNEED，二者均可释放虚拟内存与物理内存之间的映射，同时保存虚拟内存的占用。二者的区别为：前者相对智能一些，kernel 会在有内存压力时释放相应物理内存，依赖于操作系统本身的内存释放时机；而在使用后者时，kernel 会立即释放页面占用的物理内存，适用于强制释放的场景。
由于与进程的 RSS 统计息息相关，内存分配器需要谨慎使用这两个参数执行物理内存的释放，这部分将在后文阐述 jemalloc purge 的章节作详细展开。
值得一提的是，MADV_FREE 是 Linux Kernel 4.5 之后才加入的特性，落后于 FreeBSD，目前 Android 主流版本均已经支持此特性。
使用 madvise 与前文所述的使用 PROT_NONE 组合 MAP_FIXED 申请与释放内存的区别是：madvise 虽然解除了物理页面的映射，但仍然会占用 kernel mm_struct 管理的 vma 虚拟内存资源，下次再需要使用相关内存重新触发 page fault 即可；而 PROT_NONE 则不需要在 kernel 侧继续保留相应的 vma 资源，再次分配内存时需要使用 MAP_FIXED 重新 commit，产生额外的再次申请虚拟内存资源的开销。具体到 jemalloc 的使用策略是：当操作系统支持 overcommit 特性时，优先使用 madvise 保留虚拟地址空间，否则使用 decommit 的方式释放内存，munmap 并不会默认开启，这也为我们后续的 32 位进程虚拟内存优化埋下了伏笔。
Linux 用户态内存分配器
基于以上知识背景，我们可以将 Android 内存分配层级做一个划分，这里用一张图来展示：
用户进程的内存申请基本流程如下图所示：
该图取自网络，其逻辑清晰没有必要重新画了，但值得澄清的是，仔细阅读上文便会发现，针对目前的主流 Android 平台，有几处略有些瑕疵：
基于 brk 分配的 [Heap] 已被淘汰，当代内存分配器的 heap 即属于图中的 mappings，真实场景的数据 [heap] 占据比例很小。
分配内存的组函数中有一个 posix_memalign 被遗漏了，此对齐地址分配在 ffmepg 等项目中被重度使用。
释放物理内存的方法还有 madvise，这是 Android 目前最主要的释放物理内存方法，ART 虚拟机也在使用。
并非只有 [Heap] 才需触发 page fault 分配内存，所有页面都需要经历 page fault 分配物理内存。
Android 进程内存布局
通过 /proc/${pid}/smaps，我们可以对常见的 Android 进程地址空间布局做分类总结：
可以看到，在进程运行过程中，很多组件都维护了自身的内存分配器，在其地址区间上自发进行内存分配。如果是 32 位进程，要同时存在这么多内存分配器似乎略显拥挤。而且，这些内存分配器之间的信息是不互通的，可能在某一瞬间，两个内存分配器中：一个预缓存了很多内存，另外一个分配器却完全分配不出任何内存，只能触发 OOM 的情况。关于这一问题的具体解决方案将在后文详细阐述。
本文主要关注内存分配，常见的如数据库文件、字体库文件、sp 文件、mmkv 文件等在上图中未得到体现。
常见内存分配器
内存分配器的职责简洁明确，实现一个内存分配器即实现一个“堆”，上承用户态的程序，下接内核并从中申请物理资源，满足连续不断的申请与释放内存请求。那么，内存分配器是如何管理从操作系统分配的资源呢？
我们整理了常见的内存分配器算法，复杂的工业级内存分配器是多种基础内存分配器思想的组合。
bump allocator
bump allocator，在 java 虚拟机相关技术书籍里通常译为指针碰撞，也叫作 linear allocator（如在 Android hwui 里）。这是最简单也最高效的一种分配算法，设计思想很朴素，即用一个 next 指针记录当前已分配内存末尾的位置，每次申请内存时向后移动 next 指针即可，如下图：
bump allocator 设计简单但却非常高效，原因主要有三点：一是内存分配只需移动 next 指针的位置，整个过程计算量很小，仅用几条cpu指令即可；二是其分配的内存都是连续的，连续分配器的内存在使用时具有较好的局部性，这对 cpu cache 和 TLB 都很友好，相关原理可以参考下文「cache 友好程序」小节；三是其没有任何内存碎片问题的烦恼。
但 bump allocator 也存在一些问题：一是其不能释放单次分配的内存，由于只有一个 next 指针，没有保存任何其他维护已分配内存的信息，导致其不能精准释放某一次分配的内存；二是其简单的设计对多线程不友好，需要加锁才能保证程序的正确性。
bump allocator 常常作为一个 custom allocator 存在，或是内存分配器的内部组件（如 jemalloc 的 base），用于对性能有较高要求且使用场景固定的地方，具体而言即单线程运行环境且整片大块连续内存可以批量释放，例如，java 虚拟机里使用 copying gc 的内存区域执行内存分配的场景，当存活对象都从 from 区拷贝至 to 区后，from 区就可以批量释放，以及 hwui 里使用 linear allocator 分配 display list 相关内存的场景。
在 bump allocator 的基础上做一些改造：在每个内存块头部增加一个 header 存储 metadata 包含内存块释放信息和上一个内存块地址，当栈顶内存块释放时按照 LIFO 顺序依次回收内存，就可以得到一个 stack allocator，适用于释放内存与申请内存的顺序相反的场景：
freelist allocator
与 bump allocator 完全不同，freelist allocator 会把所有空闲内存（包括从未分配过的或是已释放的）组织管理起来形成一个链表，如下图：
当从 freelist 中寻找可用内存满足内存分配请求时，主要涉及三种策略：
first fit，选择第一个满足 >= requestSize 的空闲内存块
best fit，选择大小最匹配 requestSize 的空闲内存块
worst fit，选择大小最不匹配 requestSize 的空闲内存块
三种策略举例如图：
显而易见，使用 Best fit 会获得更好的内存使用率，但其查找性能开销也是最大的。这里谈及内存使用率，需要引入内存分配器领域相关的两个核心概念「内碎片」和「外碎片」，如图：
上图中，黄色区域代表已分配 page，蓝色区域代表空闲 page。碎片（fragmentation）即不停的内存分配与释放过程中带来的内存浪费，内碎片代表分配的内存块未被完美匹配利用，由尾随空间带来的碎片，比如申请分配 12 字节，jemalloc 实际会返回 16 字节的内存块，此时单针对这个内存块就会有 25% 的内碎片；外碎片代表由于空闲内存块分布分散，即使小的空闲内存块总共之和足够大，但由于空闲内存块并不连续，仍不能匹配大内存请求导致的碎片。
根除碎片的最有效的方式为内存移动整理压缩，但用户态内存分配器分配出去的虚拟内存，一旦分配不允许改变，malloc 返回的内存是要求固定不变的，所以不能依赖内存压缩解决内存分配器的虚拟内存碎片问题，内存整理压缩主要使用的领域是虚拟机 GC 与 kernel 物理内存页面反碎片，在内存分配器领域只能依靠分配算法来尽量减少虚拟内存的碎片。
不过，随着 64 位操作系统的普及和 kernel 虚拟内存页面管理相关技术软硬件的协同进步，在 Android 客户端平台以目前的内存数据量规模来看，单进程地址空间由内存分配器带来的虚拟内存的“外碎片”已经不再是令人困扰的问题，64 位地址空间解放了生产力，分配器只需考虑控制“内碎片”提升内存使用率即可，这对近年来新问世的内存分配器设计有着不小的影响，后文我们再详细讨论。
segregated freelist allocator
现代内存分配器大多使用的是在普通 freelist 的基础上迭代而来的分离式 freelist（segregated freelist），分配内存时将申请大小对应的 size class 档位，如：
{1}, {2}, {3, 4}, {5−8}, . . . , {1025−2048}, {2049−4096}, {4097−∞}
其中，大小申请在 5-8 范围内的，都会返回 8 字节；1025-2048 范围内的，都会返回 2048 字节，一个简单的示意图如下：
segregated freelist 通常每个 size class 档位都会申请一段连续内存，再将这段内存划分为多个相同大小块，并为每个 size class 档位维护一个 freelist。事实上，如果再将其和池化技术组合，我们可以得到一个简单的 slab allocator。
slab 是由 Jeff Bonwick发明的，在 Solaris 2.4 kernel 中最先应用，已有 30 余年历史，并在 Linux Kernel 中被广泛使用。在 Linux 中会通过 buddy allocator 分配物理页，为每种对象创建一个内存缓存，常见如进程描述符 task_struct 都会使用 slab allocator 分配的内存。
当然，俗话说魔鬼都在细节，slab 最复杂的点在于内存着色，详见下文中「cache 友好程序」小节。
slab的英文含义：石块
buddy allocator
buddy allocator 核心理念是：任一 的内存块可以和伙伴（buddy）合并为 的内存块，也可以拆分为两个 的内存块，在申请与释放的过程中，递归的执行拆分与合并操作。由于 buddy allocator 的内存块都是连续的，已经根除了外碎片，但由于大部分场景存在大量非 大小的内存申请，所以会造成较大的内碎片。
Linux 的 page 分配器是基于 buddy 算法的，如下为 Linux 的 page 分配函数声明：
可以从上图中看到，第二个参数是 order，直接限制了申请的 page 数量一定是 个。
jemalloc 的空闲空间分割和合并参考了 buddy allocator 算法，以期达到更好的碎片率控制，但由于 kernel 虚拟内存领域的技术进步，近十年新发布的内存分配器如 scudo/mimalloc 等其实已经不见内存块分割合并的踪影。
cache 友好程序
There are only two hard things in Computer Science: cache invalidation and naming things.
Phil Karlton
介绍计算机内存的书籍里都不可避免要谈及 cache，即嵌入 CPU 的 SRAM，和寄存器一样由门电路组成，但是结构比寄存器更简单一些，详情请查看文末参考链接。
下图是苹果 A14 Bionic 芯片 die：
可以看到，CPU cache 占据了 A14 芯片的大量晶体管，相比之下 DRAM 内存则不会有这个“待遇”，DRAM 和 SRAM 的原理不同，感兴趣的读者请查看文末参考链接。DRAM 造价成本更低，但速度也更慢，出于简单和统一考虑，本文将 DRAM 称之为内存，SRAM 称之为 cache，cache 和内存之间的访问延迟速度差异可以参考 google 大神 Jeff Dean 的数据：
Latency Comparison Numbers (~2012)----------------------------------L1 cache reference 0.5 nsBranch mispredict 5 nsL2 cache reference 7 ns 14x L1 cacheMutex lock/unlock 25 nsMain memory reference 100 ns 20x L2 cache, 200x L1 cache可以看到内存的访问速度是L1 cache的200倍、L2 cache的20倍，如果屏幕前的你想说这个数据只是2012年的x86平台的，那么如果仔细调研会发现其实ARM移动平台的内存性能更差：根据一张ARM官方本意是想彰显ARM V9提升的PPT显示，android阵营的处理器memory的延迟是150ns（好消息是据AnandTech的测试，苹果的A14处理器memory latency在100ns出头），还不如12年的PC处理器：
CPU cache和内存之间的访问延迟速度差异达百倍，cache友好的与不友好的程序效率相差一个数量级则并不足为奇，因此如何利用好 cache 的特性写好程序是一个重要课题。搞过算法竞赛的同学一定都听过一个词叫卡常数说的就是如何玩好 cache，感兴趣的读者可以搜索 cache-oblivious algorithms 相关资料。
作为离内存最近的地方，内存分配器对 cache 的影响很大，这里简单介绍两个在内存分配器设计中与 cache 相关的影响性能的典型问题：伪共享和 cache 颠簸。
伪共享：fasle cache sharing，通常 cache-line 大小为 64 字节。当多个线程访问地址相近，处于同一个 cache-line 时，会导致对 cache 所有权的争夺，无意中也影响了彼此的性能。结构体内存和 64 字节对齐能解决这个问题，但是会导致内存浪费。jemalloc 的解法是每个线程绑定自己的 Arena 物理隔离（Arena 的概念后文详细展开）。
cache 颠簸：cache thrashing，不同的内存地址映射到同一个 cache line 并且交替访问时，会触发 cache line 频繁换入换出，这个现象就叫作 cache 颠簸，造成此现象的原因与 cache 的组织形式有关。不加任何内存着色的 slab 分配器，由于地址过于整齐就会触发这个问题，所以可以看到 jemalloc 有一个 --enable-cache-oblivious 的选项来规避相关问题，此选项会默认开启。
除了 CPU Cache 之外，用于加速内存地址翻译 TLB(Translation Lookaside Buffer)也有着类似特性导致的相关问题，当CPU访问的内存地址比较连续时就会降低 TLB miss 的概率，程序会有着比较好的空间局部性，能提高地址转换的效率，也即提高 CPU 访存的效率；当出现大量物理内存解除虚拟内存映射关系时，就会降低地址转换的效率，严重时可能会触发所谓的 TLB shootdown 问题降低整机性能，文末参考链接附有一个由 jemalloc madvise 导致的 TLB shootdown 问题案例。
这些性能问题给我们的启示是：内存分配器带来的性能耗时，可能不仅限于分配时的耗时，还包括分配出去的内存的后续使用效率。
基于这些隐形性能开销背景，cache 对内存分配器的设计有重要影响，基本都会遵循以下原则：
对于应用程序短时间内连续申请的内存，内存分配器要尽量分配地址连续的内存块。
尽量避免不同线程之间短时间内分配的内存处于同一个 cache line，以及连续分配的相同大小内存映射到相同的 cache line。
在用户程序不停的内存申请与释放周期内，内存分配器要尽可能减少物理内存释放的频率，提高内存复用效率，减少寻址地址转换和重新 page fault 的开销。
内存分配小结
可以看出，Linux 内存管理机制较为繁杂，但实现基本能用的用户态内存分配器还算简单，马上就可以自己动手写一个，真正的困难在于空间与时间如何同时达到最完美的平衡点，实现一个通用的内存分配器。在探索如何实现高性能通用内存分配器过程中，笔者深刻体会了：透彻理解内存分配原理，是写出高性能程序的必经之路。
那么 jemalloc 是如何做的，快手 Android 是如何优化的，自研内存分配器能否替换掉 Android 原生的呢？请关注本系列的后续两篇文章，我们将详细阐述在内存分配器优化中“山重水复疑无路，柳暗花明又一村”的故事。
本系列文章涉及内容较多，如有纰漏，欢迎同样有志于实现 Android 内存优化的各位业界同学拍砖讨论，共同学习进步，讨论群等联系方式请移步下方链接⬇️：
https://github.com/KwaiAppTeam/KOOM
欢迎喜欢钻研技术的同学加入我们一起深入研究，北上杭深四地均有Office。
快手客户端性能稳定性团队，致力于提升快手旗下所有产品的性能和稳定性表现。欢迎热爱技术的同学们投递简历，加入我们！招聘岗位：资深Android/iOS开发工程师，base北上杭深四地。
投递邮箱：app-eng-hr@kuaishou.com，邮件标题注明【客户端性能稳定性-姓名-意向岗位】
相关链接
1.Virtual Memory Overview https://courses.cs.washington.edu/courses/cse351/19sp/lectures/23/code/vm_overview.pdf
2.madvise manual
https://man7.org/linux/man-pages/man2/madvise.2.html
3.mmap/munmap manual
https://man7.org/linux/man-pages/man2/mmap.2.html
4.Page Table
https://en.wikipedia.org/wiki/Page_table
5.The Slab Allocator: An Object-Caching Kernel Memory Allocator
https://people.eecs.berkeley.edu/~kubitron/courses/cs194-24-S14/hand-outs/bonwick_slab.pdf
6.Memory闲谈（DRAM，SRAM）
https://zhuanlan.zhihu.com/p/146094598
7.伪共享（false sharing），并发编程无声的性能杀手
https://www.cnblogs.com/cyfonly/p/5800758.html
8.深入理解 Linux 内核--jemalloc 引起的 TLB shootdown 及优化
https://gocn.vip/topics/9975
”
欢迎加入
快手主站技术部客户端团队由业界资深的移动端技术专家组成，通过领先的移动技术深耕工程架构、研发工具、动态化、数据治理等多个垂直领域，积极探索创新技术，为亿万用户打造极致体验。团队自2011年成立以来全面赋能快手生态，已经建立起业内领先的大前端技术体系，支撑快手在国内外的亿万用户。
在这里你可以获得：
提升架构设计能力和代码质量
通过大数据解决用户痛点的能力
持续优化业务架构、挑战高效研发效能
和行业大牛并肩作战
我们期待你的加入！请发简历到：
app-eng-hr@kuaishou.com
”